package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 132 模式
 */

public class Code456 {
    public static void main(String[] args) {

    }

    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;

        Deque<Integer> stack = new LinkedList<>(); // 单调递减栈
        int second = Integer.MIN_VALUE; // 记录"2"的最大值

        // 从右到左遍历
        for (int i = n - 1; i >= 0; i--) {
            // 如果当前元素小于second，说明找到了132模式
            if (nums[i] < second) {
                return true;
            }

            // 维护单调递减栈，同时更新second
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                second = Math.max(second, stack.pop());
            }

            stack.push(nums[i]);
        }

        return false;
    }
}
